package nodeList;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 2019-3-3
 * 9:39
 * 多个节点组成
 * 节点：数据＋下一个节点的地址
 * 动态数据结构
 * 客户端：不能直接使用Node节点，
 * 只需要关心数据的存储，不需关系节点间的关系
 * 因此Node作为内部类隐藏起来，
 */

/**
 * LinkedList相当于火车，具体链接每个节点
 * Node相当于火车，存储节点数据
 */
public class LinkedListImpl  {
    //头结点
    private Node head;
    private int size;

    public LinkedListImpl() {
        head = null;
        size = 0;
    }

    //每个节点类
    private class Node {
        Object data;
        Node next;//指向Node节点的引用,存放了下一节点的地址
        public Node(Object data,Node next) {
            this.data = data;
            this.next = next;
        }
        public Node(Object data) {
            this.data = data;
        }
    }

    public void addFirst(Object data) {
//        Node newNode = new Node(data);
//        newNode.next = head;
//        head = newNode;
        head = new Node(data,head);
        size++;
    }
    //在指定位置插入节点
    public void add(int index,Object data) {
        //判断下标是否合法
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index illegal...");
        }
        //判断插入点是否为第一个节点，是，则调用addFirst
        if (index == 0) {
            addFirst(data);
        } else {
            //找到index的前驱节点
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
//            Node newNode = new Node(data);//第一步
//            newNode.next = prev.next;//第二步
//            prev.next = newNode;//第三步
            prev.next = new Node(data,prev.next);
            //构造函数传值相当于第一，二步，赋值操作相当于第三步
            size++;
        }
    }


    public void add(Object data) {
        //创建新节点
        Node node = new Node(data);
        node.data = data;
        //节点拼装
    }


}
